import java.util.ArrayList;

public class RestoreIpAddresses {
    // 数字字符串转化为IP地址
    // https://www.nowcoder.com/practice/ce73540d47374dbe85b3125f57727e1e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    StringBuilder path;
    ArrayList<String> ret;
    int count = 0;
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        path = new StringBuilder();
        ret = new ArrayList<>();
        dfs(s, 0);
        return ret;
    }

    private void dfs(String s, int startIndex) {
        if (count == 4) {
            if (startIndex == s.length()) {
                ret.add(path.substring(0, path.length() - 1));
            }
            return;
        }
        for (int i = startIndex; i < startIndex + 3 && i < s.length(); i++) {
            String num = s.substring(startIndex, i+1);
            if (isValid(num)) {
                path.append(num);
                path.append(".");
                count++;
                dfs(s, i+1);
                path.delete(path.length()-num.length()-1, path.length());
                count--;
            }
        }
    }

    private boolean isValid(String s) {
        if (s.length() == 1) {
            return true;
        }
        int num = Integer.parseInt(s);
        return num >= Math.pow(10, s.length()-1) && num <= 255;
    }

    public static void main(String[] args) {
        String s = "25525522135";
        RestoreIpAddresses r = new RestoreIpAddresses();
        System.out.println(r.restoreIpAddresses(s));
    }
}
